1. Field of the Invention
The present invention relates to the design of real-time distributed embedded systems, and, in particular, to the process of partitioning an embedded system specification into hardware and software modules using hardware-software co-synthesis.
2. Description of the Related Art
Embedded systems perform application-specific functions using central processing units (CPUs). They employ both general-purpose CPUs and application-specific integrated circuits (ASICs). ASICs can be based on standard cells, gate arrays, field-programmable gate arrays (FPGAs), or complex programmable logic devices (CPLDs). An embedded system architecture consists of hardware architecture and software architecture. The hardware architecture of an embedded system defines the interconnections of various hardware components. The software architecture defines the allocation of sequences of codes to specific general-purpose processors. Hardware/software co-synthesis is a process to obtain hardware and software architectures such that various embedded system constraints such as real-time, cost, power, etc., are met. Hardware/software co-synthesis involves various steps such as allocation, scheduling, and performance estimation. Optimal hardware/software co-synthesis is known to be an NP-complete problem, where NP stands for non-deterministically polynomial. See Reference (1). Embedded systems employing reconfigurable hardware such as FPGAs and CPLDs are referred as reconfigurable embedded systems. Reconfigurable systems can provide higher performance as well as flexibility to adapt with changing system needs at low cost. See References (2)-(4). Dynamically reconfigurable embedded systems exploit reconfigurability of programmable devices at run-time to achieve further cost savings. With the availability of partially reconfigurable devices, dynamically reconfigurable systems have become viable. See References (5)-(8).
Co-synthesis of heterogeneous distributed systems has been previously addressed in References (9)-(24). Some of these co-synthesis systems (see References (12), (15), (16), (20), (23), and (24)) employ programmable devices such as FPGAs. However, none of these systems target dynamically reconfigurable embedded systems.
Dynamically reconfigurable embedded system architectures require reconfiguration of programmable hardware components such as FPGAs and CPLDs. These devices are either completely or partially reprogrammed at run-time to perform different functions at different times. Hardware/software co-synthesis of dynamically reconfigurable architectures spans three major sub-problems: 1) delay management, 2) reconfiguration management, and 3) reconfiguration interface synthesis. Delay for a circuit through a programmable device varies depending on how the constituent circuit is placed and routed. Delay management techniques ensure that the delay constraint for the specific function is not exceeded while mapping the tasks to the programmable devices. Reconfiguration management techniques identify the grouping of tasks and their allocation such that the number of reconfigurations as well as time required for each reconfiguration are minimized while ensuring that real-time constraints are met. Reconfiguration interface synthesis determines an efficient interface for reprogramming programmable devices such that cost of the system is reduced while minimizing the reconfiguration time.
The present invention is related to a heuristic-based constructive co-synthesis algorithm, CRUSADE (Co-synthesis of ReconfigUrable System Architectures of Distributed Embedded systems) which optimizes the cost of the hardware architecture while meeting the real-time and other constraints.
The present invention addresses the co-synthesis of dynamically reconfigurable architectures. Fault-tolerant distributed embedded systems can offer high performance as well as dependability (reliability) and availability to meet the needs of critical real-time applications. The present invention can be easily extended to address the needs of fault-tolerant systems. In order to establish its effectiveness, CRUSADE has been successfully applied to several large real-life examples from mobile communication network base station, video distribution router, and telecom embedded systems.
In one embodiment, the present invention is a method for designing the architecture of an embedded system, comprising a pre-processing phase, a synthesis phase, and a reconfiguration phase. The pre-processing phase comprises the step of parsing one or more task graphs, one or more system/task constraints, and a resource library for the embedded system. The synthesis phase, following the pre-processing phase, comprises the step of allocating one or more groups of one or more tasks in the tasks graphs to one or more processing elements in the resource library and allocating one or more edges in the tasks graphs to one or more communication links in the resource library, based on performance evaluation of one or more possible allocations for each of the groups and edges in light of the system/task constraints, to generate a current version of the embedded system. The reconfiguration phase, following the synthesis phase, comprises the step of generating a reconfigurable version of the embedded system by merging at least two programmable PEs of the current version of the embedded system into a composite reconfigurable programmable PE having at least two modes of operation.